#!/usr/bin/env python3
#coding:utf-8

class Node():
    COLOR_RED = 0
    COLOR_BLACK = 1
    def __init__(self, v, color = COLOR_BLACK):
        self.__v = v
        self.__color = color
        self.__left = None
        self.__right = None
        self.__parent = None
    def get_value(self):
        return self.__v
    def set_value(self, v):
        self.__v = v
    value = property(get_value, set_value)
    def set_color(self, color):
        self.__color = color
    def get_color(self):
        return self.__color
    color = property(get_color, set_color)
    def set_left(self, node):
        self.__left = node
        node.set_parent(self)
    def get_left(self):
        return self.__left
    left = property(get_left, set_left)
    def set_right(self, node):
        self.__right = node
        node.set_parent(self)
    def get_right(self):
        return self.__right
    right = property(get_right, set_right)
    def set_parent(self, node):
        self.__parent = node
    def get_parent(self):
        return self.__parent
    parent = property(get_parent, set_parent)
    def __str__(self):
        color = ['R', 'B']
        return '('+ str(self.__v) + ',' + color[self.__color] + ')'

class Tree():
    def __init__(self):
        self.NIL = Node(-1)
        self.__root = self.NIL
        self.__iter = None
        self.__iter_index = 0
        self.depth = 0
    def get_root(self):
        return self.__root
    def set_root(self, node):
        self.__root = node
        self.__root.parent = self.NIL
    root = property(get_root, set_root)
    def DFS(self):
        v = []
        def dfs(node):
            if node == self.NIL:
                return node
            v.append(node.value)
            dfs(node.left)
            dfs(node.right)
        dfs(self.__root)
        return v
    def BFS(self):
        if self.__root == self.NIL:
            return []
        v = []
        nl = [self.__root]
        while nl != []:
            nlx = []
            for n in nl:
                v.append(n.value)
                if n.left != self.NIL:
                    nlx.append(n.left)
                if n.right != self.NIL:
                    nlx.append(n.right)
            nl = nlx
        return v
            
    def insert_node(self, node):
        if self.__root is self.NIL:
            self.__root = node
            self.__root.set_parent(self.NIL)
        else:
            self.__insert_node(self.root, node)
        node.set_left(self.NIL)
        node.set_right(self.NIL)
    def __insert_node(self, root, node):
        if node.get_value() == root.get_value():
            return
        if node.get_value() < root.get_value():
            if (root.get_left() is self.NIL):
                root.set_left(node)
            else:
                self.__insert_node(root.get_left(), node)
        elif node.get_value() > root.get_value():
            if (root.get_right() is self.NIL):
                root.set_right(node)
            else:
                self.__insert_node(root.get_right(), node)
        return
    def remove_node(self, node):
        l = node.get_left()
        r = node.get_right()
        p = node.get_parent()
        if l == self.NIL:
            if node.get_value() < p.get_value():
                p.set_left(r)
            else:
                p.set_right(r)
            if r != self.NIL:
                r.set_parent(p)
        else:
            if r == self.NIL:
                if node.get_value() < p.get_value():
                    p.set_left(l)
                else:
                    p.set_right(l)
                l.set_parent(p)
            else:
                n = self.successor(node)
                node.set_value(n.get_value())
                self.remove_node(n)
    def successor(self, node):
        node = node.get_right()
        while node.get_left() != self.NIL:
            node = node.get_left()
        return node
    def preoder(self):
        a = []
        self.__preoder(a, self.__root)
        return a
    def __preoder(self, a, node):
        if node is self.NIL:
            return
        a.append(node.get_value())
        self.__preoder(a, node.get_left())
        self.__preoder(a, node.get_right())
        return
    def inoder(self):
        a = []
        self.__inoder(a, self.__root)
        return a
    def __inoder(self, a, node):
        if node is self.NIL:
            return
        self.__inoder(a, node.get_left())
        a.append(node.get_value())
        self.__inoder(a, node.get_right())
        return
    def postorder(self):
        a = []
        self.__postorder(a, self.__root)
        return a
    def __postorder(self, a, node):
        if node is self.NIL:
            return
        self.__postorder(a, node.get_left())
        self.__postorder(a, node.get_right())
        a.append(node.get_value())
        return
    def __iter__(self):
        return self
    def __next__(self):
        if self.__iter == None:
            self.__iter = []
            self.__next(self.__iter, self.__root)
            self.__iter_index = 0
        if self.__iter_index >= len(self.__iter):
            self.__iter_index = 0
            self.__iter = None
            raise StopIteration
        node = self.__iter[self.__iter_index]
        self.__iter_index += 1
        return node
    def __next(self, it, node):
        if node is self.NIL:
            return
        self.__next(it, node.get_left())
        it.append(node)
        self.__next(it, node.get_right())
        
class RBTree(Tree):
    def __init__(self):
        super().__init__()
    def insert_node(self, node):
        super().insert_node(node)
        self.__fixup_insert_node(node)
    def __fixup_insert_node(self, x):
        x.set_color(Node.COLOR_RED)
        #print(x)
        while x != self.NIL and x != self.root and x.get_parent().get_color() == Node.COLOR_RED:
            p = x.get_parent()
            pp = p.get_parent()
            if p.get_value() < pp.get_value():
                uncle = pp.get_right()
                if uncle.get_color() == Node.COLOR_RED:
                    #print('case 1')
                    p.set_color(Node.COLOR_BLACK)
                    uncle.set_color(Node.COLOR_BLACK)
                    pp.set_color(Node.COLOR_RED)
                    x = pp
                else: 
                    if x.get_value() > p.get_value():
                        #print('case 2')
                        x = p               #case 2
                        self.rotate_left(x)  
                    else:
                        #print('case 3')
                        p.set_color(Node.COLOR_BLACK) #case 3
                        pp.set_color(Node.COLOR_RED)
                        self.rotate_right(pp)
            else:
                uncle = pp.get_left()
                if uncle.get_color() == Node.COLOR_RED:
                    #print('case 4')
                    p.set_color(Node.COLOR_BLACK)   #case 4
                    uncle.set_color(Node.COLOR_BLACK)
                    pp.set_color(Node.COLOR_RED)
                    x = pp
                else:
                    if x.get_value() < p.get_value():
                        #print('case 5')
                        x = p                #case 5
                        self.rotate_right(x)  
                    else:
                        #print('case 6')
                        p.set_color(Node.COLOR_BLACK) #case 6
                        pp.set_color(Node.COLOR_RED)
                        self.rotate_left(pp)
        self.root.set_color(Node.COLOR_BLACK)
        
    def remove_node(self, node):
        if node.get_left() == self.NIL and node.get_right() == self.NIL:
            y = node
        else:
            y = super().successor(node)
        if y.get_left() != self.NIL:
            x = y.get_left()
        else:
            x = y.get_right()
        x.set_parent(y.get_parent())
        if y.get_parent() == self.NIL:
            self.root = x
        elif y == y.get_parent().get_left():
            y.get_parent().set_left(x)
        else:
            y.get_parent().set_right(x)
        if y != node:
            node.set_value(y.get_value())
        if y.get_color() == Node.COLOR_BLACK:
            self.__fixup_remove_node(x)
    def __fixup_remove_node(self, x):
        while x != self.root and x.get_color == Node.COLOR_BLACK:
            px = x.get_parent()
            if x == px.get_left():
                w = px.get_right()
                if w.get_color() == Node.COLOR_RED:
                    w.set_color(Node.COLOR_BLACK)
                    self.rotate_left(px)
                    w = px.get_right()
                if w.get_left().get_color() == Node.COLOR_BLACK and \
                    w.get_right().get_color() == Node.COLOR_BLACK:
                    w.set_color = Node.COLOR_RED
                    x = px
                elif w.get_right().get_color() == Node.COLOR_BLACK:
                    w.get_left().set_color(Node.COLOR_BLACK)
                    w.set_color(Node.COLOR_RED)
                    rotate_right(w)
                    w = px.get_right()
                else:
                    w.set_color(px.get_color())
                    px.set_color(Node.COLOR_BLACK)
                    rotate_left(px)
                    x = self.root
            else:
                w = px.get_left()
                if w.get_color() == Node.COLOR_RED:
                    w.set_color(Node.COLOR_BLACK)
                    self.rotate_right(px)
                    w = px.get_left()
                if w.get_right().get_color() == Node.COLOR_BLACK and \
                    w.get_left().get_color() == Node.COLOR_BLACK:
                    w.set_color = Node.COLOR_RED
                    x = px
                elif w.get_left().get_color() == Node.COLOR_BLACK:
                    w.get_right().set_color(Node.COLOR_BLACK)
                    w.set_color(Node.COLOR_RED)
                    rotate_left(w)
                    w = px.get_left()
                else:
                    w.set_color(px.get_color())
                    px.set_color(Node.COLOR_BLACK)
                    rotate_right(px)
                    x = self.root
    def rotate_left(self, x):
        y = x.get_right()
        if y is self.NIL:
            raise SyntaxWarning('bad rotate node left')
        p = x.get_parent()
        y.set_parent(p)
        x.set_parent(y)
        x.set_right(y.get_left())
        y.set_left(x)
        if p is self.NIL:
            self.root = y
        else:
            if x.get_value() < p.get_value():
                p.set_left(y)
            else:
                p.set_right(y)

    def rotate_right(self, y):
        x = y.get_left()
        if x is self.NIL:
            raise SyntaxWarning('bad rotate node right')
        p = y.get_parent()
        y.set_left(x.get_right())
        y.set_parent(x)
        x.set_parent(p)
        x.set_right(y)
        if p is self.NIL:
            self.root = x
        else:
            if y.get_value() < p.get_value():
                p.set_left(x)
            else:
                p.set_right(x)
        

if __name__ == '__main__':
    #tree = Tree()
    tree = RBTree()
    tree.insert_node(Node(9))
    tree.insert_node(Node(0))
    tree.insert_node(Node(1))
    tree.insert_node(Node(3))
    node1 = Node(8)
    tree.insert_node(node1)
    node2 = Node(4)
    tree.insert_node(node2)
    tree.insert_node(Node(7))
    tree.insert_node(Node(5))
    tree.insert_node(Node(2))
    tree.insert_node(Node(6))
    node3 = Node(10)
    tree.insert_node(node3)
    print('DFS:', tree.DFS())
    print('NFS:', tree.BFS())
    print('preoder:', tree.preoder())
    print('inoder:', tree.inoder())
    print('postorder:', tree.postorder())
    print('iter:')
    for n in tree:
        print(n)
    tree.remove_node(node1)
    tree.remove_node(node2)
    tree.remove_node(node3)
    print('after remove:')
    print('preoder:', tree.preoder())
    print('inoder:', tree.inoder())
    print('postorder:', tree.postorder())
    print('iter:')
    for n in tree:
        print(n, end=' ')
    print('')
